package pers.whj.util.sort;

import pers.whj.util.InvalidParamException;

public class Sort {
    private static final int USE_INSERT_SORT_FOR_QUICK_SORT = 64;
    private static final int USE_INSERT_SORT_FOR_MERGE_SORT = 50;
    private static final int MAX_DEPTH_USE_MULTI_THREAD = 8;
    private static final int MIN_COUNTS_USE_MULTI_THREAD = 100000;
    private static final int MIN_COUNTS_USE_MULTI_THREAD_FOR_OBJECT = 500000;
    private static final int COUNTING_SORT_FOR_CHAR_AND_SHORT = 1500;
    private static final int COUNTING_SORT_FOR_BYTE = 54;
    private static final float LAPSE_RATE_FOR_COMB_SORT = 1.3f;

    public static void sort(int[] data, int left, int right) {
        check(data);
        checkIndex(data.length, left, right);
        doSort(data, left, right, false, 1);
    }

    public static void sort(int[] data, int left, int right, boolean enableMultiThread) {
        check(data);
        checkIndex(data.length, left, right);
        doSort(data, left, right, enableMultiThread, 1);
    }

    private static void doSort(int[] data, int left, int right, boolean multiThread, int depth) {
        // if length is less than a value, use insert sort instead
        if (right - left < USE_INSERT_SORT_FOR_QUICK_SORT) {
            doInsertSort(data, left, right);
            return;
        }
        if (left < right) {
            // three numbers and take the middle value
            int mid = (left + right) >> 1;
            if (data[left] >= data[mid]) {
                if (data[right] <= data[mid]) {
                    int tmp = data[left];
                    data[left] = data[mid];
                    data[mid] = tmp;
                } else if (data[right] < data[left]) {
                    int tmp = data[left];
                    data[left] = data[right];
                    data[right] = tmp;
                }
            } else {
                if (data[right] >= data[mid]) {
                    int tmp = data[left];
                    data[left] = data[mid];
                    data[mid] = tmp;
                } else if (data[right] > data[left]) {
                    int tmp = data[left];
                    data[left] = data[right];
                    data[right] = tmp;
                }
            }
            // partition
            int i = left;
            int j = right;
            int pivot = data[left];
            while (i < j) {
                while (i < j && pivot <= data[j]) {
                    j--;
                }
                data[i] = data[j];
                while (i < j && pivot >= data[i]) {
                    i++;
                }
                data[j] = data[i];
            }
            data[i] = pivot;
            // recursion
            if (multiThread && depth <= MAX_DEPTH_USE_MULTI_THREAD && (right - left) >= MIN_COUNTS_USE_MULTI_THREAD) {
                final int tmp = i;
                Thread thread = new Thread(() -> doSort(data, left, tmp - 1, true, depth + 1));
                thread.start();
                doSort(data, tmp + 1, right, true, depth + 1);
                try {
                    thread.join();
                } catch (InterruptedException e) {
                    throw new RuntimeException(e);
                }
            } else {
                doSort(data, left, i - 1, false, depth + 1);
                doSort(data, i + 1, right, false, depth + 1);
            }
        }
    }

    private static void doInsertSort(int[] data, int left, int right) {
        int i, j;
        int tmp;
        for (i = left + 1; i <= right; i++) {
            tmp = data[i];
            for (j = i - 1; (j >= left) && (data[j] > tmp); j--) {
                data[j + 1] = data[j];
            }
            data[j + 1] = tmp;
        }
    }

    public static void sort(double[] data, int left, int right) {
        check(data);
        checkIndex(data.length, left, right);
        doSort(data, left, right, false, 1);
    }

    public static void sort(double[] data, int left, int right, boolean enableMultiThread) {
        check(data);
        checkIndex(data.length, left, right);
        doSort(data, left, right, enableMultiThread, 1);
    }

    private static void doSort(double[] data, int left, int right, boolean multiThread, int depth) {
        // if length is less than a value, use insert sort instead
        if (right - left < USE_INSERT_SORT_FOR_QUICK_SORT) {
            doInsertSort(data, left, right);
            return;
        }
        if (left < right) {
            // three numbers and take the middle value
            int mid = (left + right) >> 1;
            if (data[left] >= data[mid]) {
                if (data[right] <= data[mid]) {
                    double tmp = data[left];
                    data[left] = data[mid];
                    data[mid] = tmp;
                } else if (data[right] < data[left]) {
                    double tmp = data[left];
                    data[left] = data[right];
                    data[right] = tmp;
                }
            } else {
                if (data[right] >= data[mid]) {
                    double tmp = data[left];
                    data[left] = data[mid];
                    data[mid] = tmp;
                } else if (data[right] > data[left]) {
                    double tmp = data[left];
                    data[left] = data[right];
                    data[right] = tmp;
                }
            }
            // partition
            int i = left;
            int j = right;
            double pivot = data[left];
            while (i < j) {
                while (i < j && pivot <= data[j]) {
                    j--;
                }
                data[i] = data[j];
                while (i < j && pivot >= data[i]) {
                    i++;
                }
                data[j] = data[i];
            }
            data[i] = pivot;
            // recursion
            if (multiThread && depth <= MAX_DEPTH_USE_MULTI_THREAD && (right - left) >= MIN_COUNTS_USE_MULTI_THREAD) {
                final int tmp = i;
                Thread thread = new Thread(() -> doSort(data, left, tmp - 1, true, depth + 1));
                thread.start();
                doSort(data, tmp + 1, right, true, depth + 1);
                try {
                    thread.join();
                } catch (InterruptedException e) {
                    throw new RuntimeException(e);
                }
            } else {
                doSort(data, left, i - 1, false, depth + 1);
                doSort(data, i + 1, right, false, depth + 1);
            }
        }
    }

    private static void doInsertSort(double[] data, int left, int right) {
        int i, j;
        double tmp;
        for (i = left + 1; i <= right; i++) {
            tmp = data[i];
            for (j = i - 1; (j >= left) && (data[j] > tmp); j--) {
                data[j + 1] = data[j];
            }
            data[j + 1] = tmp;
        }
    }

    public static void sort(float[] data, int left, int right) {
        check(data);
        checkIndex(data.length, left, right);
        doSort(data, left, right, false, 1);
    }

    public static void sort(float[] data, int left, int right, boolean enableMultiThread) {
        check(data);
        checkIndex(data.length, left, right);
        doSort(data, left, right, enableMultiThread, 1);
    }

    private static void doSort(float[] data, int left, int right, boolean multiThread, int depth) {
        // if length is less than a value, use insert sort instead
        if (right - left < USE_INSERT_SORT_FOR_QUICK_SORT) {
            doInsertSort(data, left, right);
            return;
        }
        if (left < right) {
            // three numbers and take the middle value
            int mid = (left + right) >> 1;
            if (data[left] >= data[mid]) {
                if (data[right] <= data[mid]) {
                    float tmp = data[left];
                    data[left] = data[mid];
                    data[mid] = tmp;
                } else if (data[right] < data[left]) {
                    float tmp = data[left];
                    data[left] = data[right];
                    data[right] = tmp;
                }
            } else {
                if (data[right] >= data[mid]) {
                    float tmp = data[left];
                    data[left] = data[mid];
                    data[mid] = tmp;
                } else if (data[right] > data[left]) {
                    float tmp = data[left];
                    data[left] = data[right];
                    data[right] = tmp;
                }
            }
            // partition
            int i = left;
            int j = right;
            float pivot = data[left];
            while (i < j) {
                while (i < j && pivot <= data[j]) {
                    j--;
                }
                data[i] = data[j];
                while (i < j && pivot >= data[i]) {
                    i++;
                }
                data[j] = data[i];
            }
            data[i] = pivot;
            // recursion
            if (multiThread && depth <= MAX_DEPTH_USE_MULTI_THREAD && (right - left) >= MIN_COUNTS_USE_MULTI_THREAD) {
                final int tmp = i;
                Thread thread = new Thread(() -> doSort(data, left, tmp - 1, true, depth + 1));
                thread.start();
                doSort(data, tmp + 1, right, true, depth + 1);
                try {
                    thread.join();
                } catch (InterruptedException e) {
                    throw new RuntimeException(e);
                }
            } else {
                doSort(data, left, i - 1, false, depth + 1);
                doSort(data, i + 1, right, false, depth + 1);
            }
        }
    }

    private static void doInsertSort(float[] data, int left, int right) {
        int i, j;
        float tmp;
        for (i = left + 1; i <= right; i++) {
            tmp = data[i];
            for (j = i - 1; (j >= left) && (data[j] > tmp); j--) {
                data[j + 1] = data[j];
            }
            data[j + 1] = tmp;
        }
    }

    public static void sort(long[] data, int left, int right) {
        check(data);
        checkIndex(data.length, left, right);
        doSort(data, left, right, false, 1);
    }

    public static void sort(long[] data, int left, int right, boolean enableMultiThread) {
        check(data);
        checkIndex(data.length, left, right);
        doSort(data, left, right, enableMultiThread, 1);
    }

    private static void doSort(long[] data, int left, int right, boolean multiThread, int depth) {
        // if length is less than a value, use insert sort instead
        if (right - left < USE_INSERT_SORT_FOR_QUICK_SORT) {
            doInsertSort(data, left, right);
            return;
        }
        if (left < right) {
            // three numbers and take the middle value
            int mid = (left + right) >> 1;
            if (data[left] >= data[mid]) {
                if (data[right] <= data[mid]) {
                    long tmp = data[left];
                    data[left] = data[mid];
                    data[mid] = tmp;
                } else if (data[right] < data[left]) {
                    long tmp = data[left];
                    data[left] = data[right];
                    data[right] = tmp;
                }
            } else {
                if (data[right] >= data[mid]) {
                    long tmp = data[left];
                    data[left] = data[mid];
                    data[mid] = tmp;
                } else if (data[right] > data[left]) {
                    long tmp = data[left];
                    data[left] = data[right];
                    data[right] = tmp;
                }
            }
            // partition
            int i = left;
            int j = right;
            long pivot = data[left];
            while (i < j) {
                while (i < j && pivot <= data[j]) {
                    j--;
                }
                data[i] = data[j];
                while (i < j && pivot >= data[i]) {
                    i++;
                }
                data[j] = data[i];
            }
            data[i] = pivot;
            // recursion
            if (multiThread && depth <= MAX_DEPTH_USE_MULTI_THREAD && (right - left) >= MIN_COUNTS_USE_MULTI_THREAD) {
                final int tmp = i;
                Thread thread = new Thread(() -> doSort(data, left, tmp - 1, true, depth + 1));
                thread.start();
                doSort(data, tmp + 1, right, true, depth + 1);
                try {
                    thread.join();
                } catch (InterruptedException e) {
                    throw new RuntimeException(e);
                }
            } else {
                doSort(data, left, i - 1, false, depth + 1);
                doSort(data, i + 1, right, false, depth + 1);
            }
        }
    }

    private static void doInsertSort(long[] data, int left, int right) {
        int i, j;
        long tmp;
        for (i = left + 1; i <= right; i++) {
            tmp = data[i];
            for (j = i - 1; (j >= left) && (data[j] > tmp); j--) {
                data[j + 1] = data[j];
            }
            data[j + 1] = tmp;
        }
    }

    public static void sort(char[] data, int left, int right) {
        check(data);
        checkIndex(data.length, left, right);
        // use counting sort
        if (right - left > COUNTING_SORT_FOR_CHAR_AND_SHORT) {
            final int LENGTH = 1 << 16;
            int[] count = new int[LENGTH];
            for (int i = left; i <= right; i++) {
                count[data[i]]++;
            }
            int i = -1;
            int k = left;
            while (k <= right) {
                do {
                    i++;
                } while (count[i] == 0);
                int s = count[i];
                char value = (char) i;
                while (s > 0) {
                    data[k] = value;
                    s--;
                    k++;
                }
            }
        } else {
            // use quick sort
            doSort(data, left, right);
        }
    }

    private static void doSort(char[] data, int left, int right) {
        // if length is less than a value, use insert sort instead
        if (right - left < USE_INSERT_SORT_FOR_QUICK_SORT) {
            doInsertSort(data, left, right);
            return;
        }
        if (left < right) {
            // three numbers and take the middle value
            int mid = (left + right) >> 1;
            if (data[left] >= data[mid]) {
                if (data[right] <= data[mid]) {
                    char tmp = data[left];
                    data[left] = data[mid];
                    data[mid] = tmp;
                } else if (data[right] < data[left]) {
                    char tmp = data[left];
                    data[left] = data[right];
                    data[right] = tmp;
                }
            } else {
                if (data[right] >= data[mid]) {
                    char tmp = data[left];
                    data[left] = data[mid];
                    data[mid] = tmp;
                } else if (data[right] > data[left]) {
                    char tmp = data[left];
                    data[left] = data[right];
                    data[right] = tmp;
                }
            }
            // partition
            int i = left;
            int j = right;
            char pivot = data[left];
            while (i < j) {
                while (i < j && pivot <= data[j]) {
                    j--;
                }
                data[i] = data[j];
                while (i < j && pivot >= data[i]) {
                    i++;
                }
                data[j] = data[i];
            }
            data[i] = pivot;
            // recursion
            doSort(data, left, i - 1);
            doSort(data, i + 1, right);
        }
    }

    private static void doInsertSort(char[] data, int left, int right) {
        int i, j;
        char tmp;
        for (i = left + 1; i <= right; i++) {
            tmp = data[i];
            for (j = i - 1; (j >= left) && (data[j] > tmp); j--) {
                data[j + 1] = data[j];
            }
            data[j + 1] = tmp;
        }
    }

    public static void sort(short[] data, int left, int right) {
        check(data);
        checkIndex(data.length, left, right);
        // use counting sort
        if (right - left > COUNTING_SORT_FOR_CHAR_AND_SHORT) {
            final int LENGTH = 1 << 16;
            int[] count = new int[LENGTH];
            for (int i = left; i <= right; i++) {
                count[data[i] - Short.MIN_VALUE]++;
            }
            int i = -1;
            int k = left;
            while (k <= right) {
                do {
                    i++;
                } while (count[i] == 0);
                int s = count[i];
                short value = (short) (i + Short.MIN_VALUE);
                while (s > 0) {
                    data[k] = value;
                    s--;
                    k++;
                }
            }
        } else {
            // use quick sort
            doSort(data, left, right);
        }
    }

    private static void doSort(short[] data, int left, int right) {
        // if length is less than a value, use insert sort instead
        if (right - left < USE_INSERT_SORT_FOR_QUICK_SORT) {
            doInsertSort(data, left, right);
            return;
        }
        if (left < right) {
            // three numbers and take the middle value
            int mid = (left + right) >> 1;
            if (data[left] >= data[mid]) {
                if (data[right] <= data[mid]) {
                    short tmp = data[left];
                    data[left] = data[mid];
                    data[mid] = tmp;
                } else if (data[right] < data[left]) {
                    short tmp = data[left];
                    data[left] = data[right];
                    data[right] = tmp;
                }
            } else {
                if (data[right] >= data[mid]) {
                    short tmp = data[left];
                    data[left] = data[mid];
                    data[mid] = tmp;
                } else if (data[right] > data[left]) {
                    short tmp = data[left];
                    data[left] = data[right];
                    data[right] = tmp;
                }
            }
            // partition
            int i = left;
            int j = right;
            short pivot = data[left];
            while (i < j) {
                while (i < j && pivot <= data[j]) {
                    j--;
                }
                data[i] = data[j];
                while (i < j && pivot >= data[i]) {
                    i++;
                }
                data[j] = data[i];
            }
            data[i] = pivot;
            // recursion
            doSort(data, left, i - 1);
            doSort(data, i + 1, right);
        }
    }

    private static void doInsertSort(short[] data, int left, int right) {
        int i, j;
        short tmp;
        for (i = left + 1; i <= right; i++) {
            tmp = data[i];
            for (j = i - 1; (j >= left) && (data[j] > tmp); j--) {
                data[j + 1] = data[j];
            }
            data[j + 1] = tmp;
        }
    }

    public static void sort(byte[] data, int left, int right) {
        check(data);
        checkIndex(data.length, left, right);
        // use counting sort
        if (right - left > COUNTING_SORT_FOR_BYTE) {
            final int LENGTH = 1 << 8;
            int[] count = new int[LENGTH];
            for (int i = left; i <= right; i++) {
                count[data[i] - Byte.MIN_VALUE]++;
            }
            int i = -1;
            int k = left;
            while (k <= right) {
                do {
                    i++;
                } while (count[i] == 0);
                int s = count[i];
                byte value = (byte) (i + Byte.MIN_VALUE);
                while (s > 0) {
                    data[k] = value;
                    s--;
                    k++;
                }
            }
        } else {
            // use quick sort
            doInsertSort(data, left, right);
        }
    }

    private static void doInsertSort(byte[] data, int left, int right) {
        int i, j;
        byte tmp;
        for (i = left + 1; i <= right; i++) {
            tmp = data[i];
            for (j = i - 1; (j >= left) && (data[j] > tmp); j--) {
                data[j + 1] = data[j];
            }
            data[j + 1] = tmp;
        }
    }

    public static void sort(Object[] data, int left, int right) {
        check(data);
        checkIndex(data.length, left, right);
        doSort(data, left, right, false, 1);
    }

    public static void sort(Object[] data, int left, int right, boolean enableMultiThread) {
        check(data);
        checkIndex(data.length, left, right);
        doSort(data, left, right, enableMultiThread, 1);
    }

    @SuppressWarnings({"rawtypes", "unchecked"})
    private static void doSort(Object[] data, int left, int right, boolean multiThread, int depth) {
        // if length is less than a value, use insert sort instead
        if (right - left < USE_INSERT_SORT_FOR_QUICK_SORT) {
            doInsertSort(data, left, right);
            return;
        }
        if (left < right) {
            // three numbers and take the middle value
            int mid = (left + right) >> 1;
            Comparable l = (Comparable) data[left];
            Comparable m = (Comparable) data[mid];
            Comparable r = (Comparable) data[right];
            if (l.compareTo(m) >= 0) {
                if (r.compareTo(m) <= 0) {
                    Object tmp = data[left];
                    data[left] = data[mid];
                    data[mid] = tmp;
                } else if (r.compareTo(l) < 0) {
                    Object tmp = data[left];
                    data[left] = data[right];
                    data[right] = tmp;
                }
            } else {
                if (r.compareTo(m) >= 0) {
                    Object tmp = data[left];
                    data[left] = data[mid];
                    data[mid] = tmp;
                } else if (r.compareTo(l) > 0) {
                    Object tmp = data[left];
                    data[left] = data[right];
                    data[right] = tmp;
                }
            }
            // partition
            int i = left;
            int j = right;
            Comparable pivot = (Comparable) data[left];
            while (i < j) {
                while (i < j && pivot.compareTo(data[j]) <= 0) {
                    j--;
                }
                data[i] = data[j];
                while (i < j && pivot.compareTo(data[i]) >= 0) {
                    i++;
                }
                data[j] = data[i];
            }
            data[i] = pivot;
            // recursion
            if (multiThread && depth <= MAX_DEPTH_USE_MULTI_THREAD && (right - left) >= MIN_COUNTS_USE_MULTI_THREAD_FOR_OBJECT) {
                final int tmp = i;
                Thread thread = new Thread(() -> doSort(data, left, tmp - 1, true, depth + 1));
                thread.start();
                doSort(data, tmp + 1, right, true, depth + 1);
                try {
                    thread.join();
                } catch (InterruptedException e) {
                    throw new RuntimeException(e);
                }
            } else {
                doSort(data, left, i - 1, false, depth + 1);
                doSort(data, i + 1, right, false, depth + 1);
            }
        }
    }

    @SuppressWarnings({"rawtypes", "unchecked"})
    private static void doInsertSort(Object[] data, int left, int right) {
        int i, j;
        Comparable tmp;
        for (i = left + 1; i <= right; i++) {
            tmp = (Comparable) data[i];
            for (j = i - 1; (j >= left) && (tmp.compareTo(data[j]) < 0); j--) {
                data[j + 1] = data[j];
            }
            data[j + 1] = tmp;
        }
    }

    /**
     * 冒泡排序
     */
    public static void bubbleSort(int[] data, int left, int right) {
        check(data);
        checkIndex(data.length, left, right);
        boolean flag;
        for (int i = left + 1; i <= right; i++) {
            flag = false;
            for (int j = right; j >= i; j--) {
                if (data[j - 1] > data[j]) {
                    int temp = data[j - 1];
                    data[j - 1] = data[j];
                    data[j] = temp;
                    flag = true;
                }
            }
            if (!flag) {
                break;
            }
        }
    }

    /**
     * 梳排序
     */
    public static void combSort(int[] data, int left, int right) {
        check(data);
        checkIndex(data.length, left, right);
        int i, j, tmp;
        int gap = right - left + 1;
        boolean flag;
        do {
            flag = false;
            gap = (int) (gap / LAPSE_RATE_FOR_COMB_SORT);
            if (gap < 1) {
                gap = 1;
            }
            for (i = left; i <= right - gap; i++) {
                j = i + gap;
                if (data[i] > data[j]) {
                    tmp = data[i];
                    data[i] = data[j];
                    data[j] = tmp;
                    flag = true;
                }
            }
        } while (gap > 1 || flag);
    }

    /**
     * 选择排序
     */
    public static void selectSort(int[] data, int left, int right) {
        check(data);
        checkIndex(data.length, left, right);
        for (int i = left; i < right; i++) {
            int k = i;
            for (int j = i + 1; j <= right; j++) {
                if (data[k] > data[j]) {
                    k = j;
                }
            }
            if (k != i) {
                int temp = data[i];
                data[i] = data[k];
                data[k] = temp;
            }
        }
    }

    public static void deSelectSort(int[] data, int left, int right) {
        check(data);
        checkIndex(data.length, left, right);
        // select min and max one turn
        int min, max, tmp;
        while (left < right) {
            min = left;
            max = right;
            if (data[min] > data[max]) {
                tmp = data[min];
                data[min] = data[max];
                data[max] = tmp;
            }
            for (int i = left + 1; i < right; i++) {
                if (data[i] < data[min]) {
                    min = i;
                } else if (data[i] > data[max]) {
                    max = i;
                }
            }
            if (min != left) {
                tmp = data[min];
                data[min] = data[left];
                data[left] = tmp;
            }
            if (max != right) {
                tmp = data[max];
                data[max] = data[right];
                data[right] = tmp;
            }
            left++;
            right--;
        }
    }

    /**
     * 插入排序
     */
    public static void insertSort(int[] data, int left, int right) {
        check(data);
        checkIndex(data.length, left, right);
        int tmp;
        for (int i = left + 1; i <= right; i++) {
            tmp = data[i];
            int j = i - 1;
            while (j >= left && data[j] > tmp) {
                data[j + 1] = data[j];
                j--;
            }
            data[j + 1] = tmp;
        }
    }

    public static void binaryInsertSort(int[] data, int left, int right) {
        check(data);
        checkIndex(data.length, left, right);
        int tmp, low, mid, high;
        for (int i = left + 1; i <= right; i++) {
            tmp = data[i];
            low = left;
            high = i - 1;
            while (low <= high) {
                mid = (low + high) >> 1;
                if (data[mid] > tmp) {
                    high = mid - 1;
                } else {
                    low = mid + 1;
                }
            }
            int len = i - high - 1;
            if (len > 0) {
                System.arraycopy(data, high + 1, data, high + 2, len);
                data[high + 1] = tmp;
            }
        }
    }

    /**
     * 希尔排序
     */
    public static void shellSort(int[] data, int left, int right) {
        check(data);
        checkIndex(data.length, left, right);
        int gap = right - left + 1;
        int i, j, tmp;
        do {
            gap = gap / 3 + 1;
            for (i = left + gap; i <= right; i++) {
                tmp = data[i];
                j = i - gap;
                while (j >= left && data[j] > tmp) {
                    data[j + gap] = data[j];
                    j -= gap;
                }
                data[j + gap] = tmp;
            }
        } while (gap > 1);
    }

    /**
     * 堆排序
     */
    public static void heapSort(int[] data, int left, int right) {
        check(data);
        checkIndex(data.length, left, right);
        for (int i = (right - left - 1) / 2; i >= 0; i--) {
            siftDown(data, i, right - left, left);
        }
        for (int i = right - left; i > 0; i--) {
            int temp = data[left];
            data[left] = data[left + i];
            data[left + i] = temp;
            siftDown(data, 0, i - 1, left);
        }
    }

    private static void siftDown(int[] data, int start, int end, int offset) {
        int j = 2 * start + 1;
        int tmp = data[start + offset];
        int target;
        while (j <= end) {
            target = j + offset;
            if (j < end && data[target] < data[target + 1]) {
                j++;
                target++;
            }
            if (tmp >= data[target]) {
                break;
            } else {
                data[start + offset] = data[target];
                start = j;
                j = 2 * j + 1;
            }
        }
        data[start + offset] = tmp;
    }

    /**
     * 归并排序
     */
    public static void mergeSort(int[] data, int left, int right) {
        check(data);
        checkIndex(data.length, left, right);
        doMergeSort(data, left, right);
    }

    /**
     * 归并排序（多线程）
     */
    public static void mergeSort(int[] data, int left, int right, boolean enableMultiThread) {
        check(data);
        checkIndex(data.length, left, right);
        doMergeSort(data, left, right, enableMultiThread, 1);
    }

    private static void doMergeSort(int[] data, int left, int right) {
        if (right - left < USE_INSERT_SORT_FOR_MERGE_SORT) {
            doInsertSort(data, left, right);
            return;
        }
        if (left < right) {
            int mid = (right + left) / 2;
            doMergeSort(data, left, mid);
            doMergeSort(data, mid + 1, right);
            if (data[mid] <= data[mid + 1]) {
                return;
            }
            // merge steps
            int leftBorder = mid - left;
            int rightBorder = right - left;
            // extra space
            int[] temp = new int[rightBorder + 1];
            System.arraycopy(data, left, temp, 0, temp.length);
            int s1 = 0;
            int s2 = leftBorder + 1;
            int s = left;
            while (s1 <= leftBorder && s2 <= rightBorder) {
                if (temp[s1] > temp[s2]) {
                    data[s++] = temp[s2++];
                } else {
                    data[s++] = temp[s1++];
                }
            }
            while (s1 <= leftBorder) {
                data[s++] = temp[s1++];
            }
            while (s2 <= rightBorder) {
                data[s++] = temp[s2++];
            }
        }
    }

    private static void doMergeSort(int[] data, int left, int right, boolean multiThread, int depth) {
        if (right - left < USE_INSERT_SORT_FOR_MERGE_SORT) {
            doInsertSort(data, left, right);
            return;
        }
        if (left < right) {
            int mid = (right + left) / 2;
            if (multiThread && depth <= MAX_DEPTH_USE_MULTI_THREAD && (right - left) >= MIN_COUNTS_USE_MULTI_THREAD) {
                Thread thread = new Thread(() -> doMergeSort(data, left, mid, true, depth + 1));
                thread.start();
                doMergeSort(data, mid + 1, right, true, depth + 1);
                try {
                    thread.join();
                } catch (InterruptedException e) {
                    throw new RuntimeException(e);
                }
            } else {
                doMergeSort(data, left, mid, false, depth + 1);
                doMergeSort(data, mid + 1, right, false, depth + 1);
            }
            if (data[mid] <= data[mid + 1]) {
                return;
            }
            // merge steps
            int leftBorder = mid - left;
            int rightBorder = right - left;
            // extra space
            int[] temp = new int[rightBorder + 1];
            System.arraycopy(data, left, temp, 0, temp.length);
            int s1 = 0;
            int s2 = leftBorder + 1;
            int s = left;
            while (s1 <= leftBorder && s2 <= rightBorder) {
                if (temp[s1] > temp[s2]) {
                    data[s++] = temp[s2++];
                } else {
                    data[s++] = temp[s1++];
                }
            }
            while (s1 <= leftBorder) {
                data[s++] = temp[s1++];
            }
            while (s2 <= rightBorder) {
                data[s++] = temp[s2++];
            }
        }
    }

    /**
     * 鸡尾酒排序
     */
    public static void cocktailSort(int[] data, int left, int right) {
        check(data);
        checkIndex(data.length, left, right);
        boolean flag = true;
        int start = left;
        int end = right;
        int tmp;
        while (flag) {
            flag = false;
            for (int i = start; i < end; i++) {
                if (data[i] > data[i + 1]) {
                    tmp = data[i];
                    data[i] = data[i + 1];
                    data[i + 1] = tmp;
                    flag = true;
                }
            }
            end--;
            for (int i = end; i > start; i--) {
                if (data[i] < data[i - 1]) {
                    tmp = data[i];
                    data[i] = data[i - 1];
                    data[i - 1] = tmp;
                    flag = true;
                }
            }
            start++;
        }
    }

    /**
     * 奇偶排序
     */
    public static void oddEvenSort(int[] data, int left, int right) {
        check(data);
        checkIndex(data.length, left, right);
        boolean unsorted = true;
        int i, tmp;
        while (unsorted) {
            unsorted = false;
            for (i = left + 1; i <= right - 1; i += 2) {
                if (data[i] > data[i + 1]) {
                    tmp = data[i];
                    data[i] = data[i + 1];
                    data[i + 1] = tmp;
                    unsorted = true;
                }
            }
            for (i = left; i <= right - 1; i += 2) {
                if (data[i] > data[i + 1]) {
                    tmp = data[i];
                    data[i] = data[i + 1];
                    data[i + 1] = tmp;
                    unsorted = true;
                }
            }
        }
    }

    /**
     * 臭皮匠排序，很慢
     */
    public static void stoogeSort(int[] data, int left, int right) {
        check(data);
        checkIndex(data.length, left, right);
        doStoogeSort(data, left, right);
    }

    private static void doStoogeSort(int[] data, int left, int right) {
        if (data[left] > data[right]) {
            int tmp = data[left];
            data[left] = data[right];
            data[right] = tmp;
        }
        if ((right - left + 1) >= 3) {
            int split = (right - left + 1) / 3;
            doStoogeSort(data, left, right - split);
            doStoogeSort(data, left + split, right);
            doStoogeSort(data, left, right - split);
        }
    }

    /**
     * 计数排序，数字范围不宜过大
     */
    public static void countingSort(int[] data, int left, int right, int minValue, int maxValue) {
        check(data);
        checkIndex(data.length, left, right);
        final int LENGTH = maxValue - minValue + 1;
        int[] count = new int[LENGTH];
        for (int i = left; i <= right; i++) {
            count[data[i] - minValue]++;
        }
        int i = -1;
        int k = left;
        while (k <= right) {
            do {
                i++;
            } while (count[i] == 0);
            int s = count[i];
            int value = i + minValue;
            while (s > 0) {
                data[k] = value;
                s--;
                k++;
            }
        }
    }

    /**
     * 地精排序
     */
    public static void gnomeSort(int[] data, int left, int right) {
        check(data);
        checkIndex(data.length, left, right);
        int i = left + 1;
        int tmp;
        while (i <= right) {
            if (i > left && data[i - 1] > data[i]) {
                tmp = data[i - 1];
                data[i - 1] = data[i];
                data[i] = tmp;
                i--;
            } else {
                i++;
            }
        }
    }

     /**
     * 逆置数组
     */
    public static void reverse(int[] data, int left, int right) {
        check(data);
        checkIndex(data.length, left, right);
        int tmp;
        while (left < right) {
            tmp = data[left];
            data[left] = data[right];
            data[right] = tmp;
            left++;
            right--;
        }
    }

    /**
     * 逆置数组
     */
    public static void reverse(double[] data, int left, int right) {
        check(data);
        checkIndex(data.length, left, right);
        double tmp;
        while (left < right) {
            tmp = data[left];
            data[left] = data[right];
            data[right] = tmp;
            left++;
            right--;
        }
    }

    /**
     * 逆置数组
     */
    public static void reverse(float[] data, int left, int right) {
        check(data);
        checkIndex(data.length, left, right);
        float tmp;
        while (left < right) {
            tmp = data[left];
            data[left] = data[right];
            data[right] = tmp;
            left++;
            right--;
        }
    }

    /**
     * 逆置数组
     */
    public static void reverse(long[] data, int left, int right) {
        check(data);
        checkIndex(data.length, left, right);
        long tmp;
        while (left < right) {
            tmp = data[left];
            data[left] = data[right];
            data[right] = tmp;
            left++;
            right--;
        }
    }

    /**
     * 逆置数组
     */
    public static void reverse(char[] data, int left, int right) {
        check(data);
        checkIndex(data.length, left, right);
        char tmp;
        while (left < right) {
            tmp = data[left];
            data[left] = data[right];
            data[right] = tmp;
            left++;
            right--;
        }
    }

    /**
     * 逆置数组
     */
    public static void reverse(short[] data, int left, int right) {
        check(data);
        checkIndex(data.length, left, right);
        short tmp;
        while (left < right) {
            tmp = data[left];
            data[left] = data[right];
            data[right] = tmp;
            left++;
            right--;
        }
    }

    /**
     * 逆置数组
     */
    public static void reverse(byte[] data, int left, int right) {
        check(data);
        checkIndex(data.length, left, right);
        byte tmp;
        while (left < right) {
            tmp = data[left];
            data[left] = data[right];
            data[right] = tmp;
            left++;
            right--;
        }
    }

    /**
     * 逆置数组
     */
    public static void reverse(Object[] data, int left, int right) {
        check(data);
        checkIndex(data.length, left, right);
        Object tmp;
        while (left < right) {
            tmp = data[left];
            data[left] = data[right];
            data[right] = tmp;
            left++;
            right--;
        }
    }

    /**
     * 检查数组是否顺序（逆序）
     */
    public static boolean sorted(int[] data, int left, int right, boolean reverseOrder) {
        check(data);
        checkIndex(data.length, left, right);
        if (reverseOrder) {
            while (left < right) {
                if (data[left] < data[left + 1]) {
                    return false;
                }
                left++;
            }
        } else {
            while (left < right) {
                if (data[left] > data[left + 1]) {
                    return false;
                }
                left++;
            }
        }
        return true;
    }

    /**
     * 检查数组是否顺序（逆序）
     */
    public static boolean sorted(double[] data, int left, int right, boolean reverseOrder) {
        check(data);
        checkIndex(data.length, left, right);
        if (reverseOrder) {
            while (left < right) {
                if (data[left] < data[left + 1]) {
                    return false;
                }
                left++;
            }
        } else {
            while (left < right) {
                if (data[left] > data[left + 1]) {
                    return false;
                }
                left++;
            }
        }
        return true;
    }

    /**
     * 检查数组是否顺序（逆序）
     */
    public static boolean sorted(float[] data, int left, int right, boolean reverseOrder) {
        check(data);
        checkIndex(data.length, left, right);
        if (reverseOrder) {
            while (left < right) {
                if (data[left] < data[left + 1]) {
                    return false;
                }
                left++;
            }
        } else {
            while (left < right) {
                if (data[left] > data[left + 1]) {
                    return false;
                }
                left++;
            }
        }
        return true;
    }

    /**
     * 检查数组是否顺序（逆序）
     */
    public static boolean sorted(long[] data, int left, int right, boolean reverseOrder) {
        check(data);
        checkIndex(data.length, left, right);
        if (reverseOrder) {
            while (left < right) {
                if (data[left] < data[left + 1]) {
                    return false;
                }
                left++;
            }
        } else {
            while (left < right) {
                if (data[left] > data[left + 1]) {
                    return false;
                }
                left++;
            }
        }
        return true;
    }

    /**
     * 检查数组是否顺序（逆序）
     */
    public static boolean sorted(char[] data, int left, int right, boolean reverseOrder) {
        check(data);
        checkIndex(data.length, left, right);
        if (reverseOrder) {
            while (left < right) {
                if (data[left] < data[left + 1]) {
                    return false;
                }
                left++;
            }
        } else {
            while (left < right) {
                if (data[left] > data[left + 1]) {
                    return false;
                }
                left++;
            }
        }
        return true;
    }

    /**
     * 检查数组是否顺序（逆序）
     */
    public static boolean sorted(short[] data, int left, int right, boolean reverseOrder) {
        check(data);
        checkIndex(data.length, left, right);
        if (reverseOrder) {
            while (left < right) {
                if (data[left] < data[left + 1]) {
                    return false;
                }
                left++;
            }
        } else {
            while (left < right) {
                if (data[left] > data[left + 1]) {
                    return false;
                }
                left++;
            }
        }
        return true;
    }

    /**
     * 检查数组是否顺序（逆序）
     */
    public static boolean sorted(byte[] data, int left, int right, boolean reverseOrder) {
        check(data);
        checkIndex(data.length, left, right);
        if (reverseOrder) {
            while (left < right) {
                if (data[left] < data[left + 1]) {
                    return false;
                }
                left++;
            }
        } else {
            while (left < right) {
                if (data[left] > data[left + 1]) {
                    return false;
                }
                left++;
            }
        }
        return true;
    }

    /**
     * 检查数组是否顺序（逆序）
     */
    @SuppressWarnings({"rawtypes", "unchecked"})
    public static boolean sorted(Object[] data, int left, int right, boolean reverseOrder) {
        check(data);
        checkIndex(data.length, left, right);
        if (reverseOrder) {
            while (left < right) {
                if (((Comparable) data[left]).compareTo(data[left + 1]) < 0) {
                    return false;
                }
                left++;
            }
        } else {
            while (left < right) {
                if (((Comparable) data[left]).compareTo(data[left + 1]) > 0) {
                    return false;
                }
                left++;
            }
        }
        return true;
    }

    private static void check(Object array) {
        if (array == null) {
            throw new RuntimeException("array is null");
        }
    }

    private static void checkIndex(int arrayLength, int left, int right) {
        if (left > right) {
            throw new InvalidParamException("array: left > right, left: " + left + " right: " + right);
        }
        if (left < 0) {
            throw new IndexOutOfBoundsException("length: " + arrayLength + " left index: " + left);
        }
        if (right >= arrayLength) {
            throw new IndexOutOfBoundsException("length: " + arrayLength + " right index: " + right);
        }
    }
}